The technical field of this invention is data processing and, in particular, memory management for multiple user systems that employ demand paging and a virtual memory architecture.
Data processing systems generally include a central processing unit ("CPU"), a storage system (or "main memory"), peripheral devices and associated interfaces. Typically, the main memory consists of relatively low cost, high-capacity, digital storage devices. The peripheral device may be, for example, a non-volatile auxiliary memory medium, such as a magnetic disk or magnetic tape drive.
In order to carry out tasks, the central processing unit of such systems executes a succession of instructions which operate on data. The succession of instructions and the data those instructions reference are referred to as a program. The execution of a program by the central processing unit is referred to as a process. The address space that contains the instructions and data for a process is called the process image. A process image typically is distributed between the main memory and the auxiliary memory, depending upon the size of the process and the immediate needs of the central processing unit.
An architecture called virtual memory is employed in many data processing systems where service is provided to a number of users. On some systems, virtual memory is divided into segments, each of which is further divided into pages with each page accomodating a fixed number of words. In a number of systems, for example, the Series 50 systems manufactured by Prime Computer, Inc. of Natick, Massachusetts, the addresses of the segments and pages are allocated by an operating system and can be arranged in the main memory in a random fashion. To the user, however, an appearance of continuity and unlimited memory space is presented and the user need not be concerned with the actual interleaved nature of programs in the main memory. Moreover, at any given time some pages of a program may reside in the auxiliary memory rather than the main memory. Page maps and the like, are employed by the operating system to translate virtual memory addresses into physical locations in main or auxiliary memory.
When a process begins, it is necessary to retrieve pages containing instructions or data from memory. When a page of a program is needed by a process but is not resident in main memory, a "page fault" occurs. Demand paging refers to a method of fetching pages from auxiliary memory. Demand paging systems transport just one page (containing the next instruction to be executed or data to be manipulated) into main memory at a time. A replacement policy is typically employed by the operating system at the same time to "page out" instructions or data that are not likely to be needed again in the near future. For example, the least recently used page can be transferred from main memory to auxiliary memory. Each time a page is transferred from one memory location to another, the address and page maps must be revised accordingly.
One operating system which has gained widespread acceptance in the industry is the UNIX operating system. (UNIX is a trademark of the AT&T Bell Laboratories). The UNIX system is designed to be "portable", that is to say, programs coded to interface with UNIX on one data processing system can be run on other hardware as well. Many of the data processing systems currently being manufactured employ either the UNIX operating system or an operating system that emulates UNIX functions. The Prime Computer Series 50 systems, for example, can be configured to run PRIMIX, a UNIX emulation which operates in conjunction with the Series 50 system's PRIMOS operating system. (PRIMIX and PRIMOS are trademarks of Prime Computer, Inc.).
UNIX is a multi-user, time-sharing, operating system using a tree-structured file system. Other noteworthy functional features are its logical I/O capabilities, pipes, and forks. "Logical I/O" allows the user to specify the input and output files of a program at runtime rather than at compile time, thus providing greater flexibility. "Piping" is a UNIX feature which allows the buffering of input and output to and from other processes. "Forking" is a UNIX method for creating new processes.
By themselves, these UNIX features offer no inherent benefits. However, the UNIX command environment (called the SHELL) provides easy access to these operating system capabilities and also allows them to be used in different combinations. With the proper selection and ordering of system commands, logical I/O, pipes, and forks, a UNIX user at command level can accomplish work which on another system would require writing and generating an entirely new program. This ability to easily create application program equivalents from command level is one of the unique and primary benefits of the UNIX operating system.
A problem can often arise when a UNIX-type operating system is implemented in a multiple user environment. The basic operation of a "fork" in the UNIX system involves spawning a new process, and then copying the process image of the parent (the process making the fork call) to the child (the newly spawned process). The time required to copy over a process image is proportional to the size of the process image. Therefore, a generic problem of running a UNIX-type system on a large virtual memory CPU architecture, is that the process image copy time of a fork operation can be a performance bottleneck.
The performance problem is further aggravated in a multi-user environment because many fork operations are taking place simultaneously. Each page fault generated while copying the process image from parent to child can potentially displace a page in another process, indirectly causing the other process to incur more page faults when it runs. Thus, the incremental paging caused by each fork operation can dramatically increase the overall paging rate of the system. The end result can be very poor performance when the system is heavily used. This problem is typically referred to as "thrashing".
There exists a need for better methods and systems of memory management, particularly when UNIX-type operating systems are employed in multiple user, virtual memory architectures. A memory management system that can reduce the performance bottlenecks and potential thrashing associated with UNIX fork operations, would satisfy a substantial need in the industry.